package net.lee.algorithm.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class TreeOrder {

    public static void main(String args[])
    {
       TreeNode root =  TreeInfo.getTree();
       List<TreeNode> treeNodeList = new ArrayList<>();
        Stack<TreeNode> treeNodes = new Stack<>();
        treeNodes.push(root);
        treeOrderLast(treeNodes,treeNodeList);
        for (TreeNode treeNode:treeNodeList
             ) {
            System.out.print(treeNode.getValue()+" - ");
        }
    }

    /**
     *  先序遍历
     */
    public static void treeOrderFirst(TreeNode treeNode,List<TreeNode> treeNodeList)
    {


        treeNodeList.add(treeNode);
        if (treeNode.getLeftNode()!=null)
        {
            treeOrderFirst(treeNode.getLeftNode(),treeNodeList);
        }
        if(treeNode.getRightNode()!=null)
        {
            treeOrderFirst(treeNode.getRightNode(),treeNodeList);
        }

    }

    /**
     * 中序遍历
     * @param treeNodeList
     */
    public static void treeOrderMiddle(Stack<TreeNode> treeNodeStack,List<TreeNode> treeNodeList)
    {
        // Stack<TreeNode> treeNodeStack = new Stack<>();
        TreeNode treeNode = treeNodeStack.pop();
        while (treeNode.getLeftNode()!=null&& !treeNodeList.contains(treeNode.getLeftNode()))
        {
            if(!treeNodeStack.contains(treeNode))
            {
                treeNodeStack.push(treeNode);
            }
            treeNode = treeNode.getLeftNode();

        }
        if(treeNodeList!=null && !treeNodeList.contains(treeNode))
        {
            treeNodeList.add(treeNode);
        }
        if(treeNode.getRightNode()!=null && !treeNodeList.contains(treeNode.getRightNode()))
        {
            if(!treeNodeStack.contains(treeNode.getRightNode()))
            {
                treeNodeStack.push(treeNode.getRightNode());
                if(treeNode.getRightNode().getLeftNode()==null)
                {
                    treeNodeList.add(treeNode.getRightNode());
                }
            }


        }

        if(!treeNodeStack.isEmpty())
        {
            // treeNode = treeNodeStack.pop();
            treeOrderMiddle(treeNodeStack,treeNodeList);

        }

    }

    public static void treeOrderLast(Stack<TreeNode> treeNodeStack,List<TreeNode> treeNodeList)
    {
        TreeNode treeNode = treeNodeStack.pop();
        while (treeNode.getLeftNode()!=null&& !treeNodeList.contains(treeNode.getLeftNode()))
        {
            if(!treeNodeStack.contains(treeNode))
            {
                treeNodeStack.push(treeNode);
            }
            treeNode = treeNode.getLeftNode();
        }
        if(treeNode.getRightNode()!=null&&!treeNodeList.contains(treeNode.getRightNode()))
        {
            if(!treeNodeStack.contains(treeNode))
            {
                treeNodeStack.push(treeNode);
            }
            treeNodeStack.push(treeNode.getRightNode());
        }
        if(treeNodeList.contains(treeNode.getRightNode())||treeNode.getRightNode()==null)
        {
            treeNodeList.add(treeNode);
        }
        if(!treeNodeStack.isEmpty())
        {
            // treeNode = treeNodeStack.pop();
            treeOrderLast(treeNodeStack,treeNodeList);

        }
    }
}
